package com.gitee.wsl.text.replacer

import com.gitee.wsl.ext.coroutines.synchronize
import kotlinx.atomicfu.locks.SynchronizedObject

//https://my.oschina.net/u/4090830/blog/18059068
/**
 *实现的 Trie 树的性能是最好的，因为只做了替换的逻辑，没有实现其他功能
 */
class TrieKeywordReplacer(keyWords: String,val repToString: String = ""):StrReplacer {
    private val trie: Trie

     override fun replace(text: CharSequence): String {
        return trie.replaceKeywords(text, repToString)
    }

    init {
        val trie = Trie()
        for (s in keyWords.split(";".toRegex()).dropLastWhile { it.isEmpty() }.toTypedArray()) {
            trie.insert(s)
        }
        this.trie = trie
    }

    internal class TrieNode {
        var children: MutableMap<Char, TrieNode?> = HashMap()
        var isEndOfWord: Boolean = false
    }

    internal class Trie: SynchronizedObject() {
        private val root = TrieNode()

        internal fun insert(word: String) = synchronize {
            var node: TrieNode? = root
            for (c in word.toCharArray()) {
                if (node!!.children[c] == null) {
                    node.children[c] = TrieNode()
                }
                node = node.children[c]
            }
            node!!.isEndOfWord = true
        }

        fun replaceKeywords(text: CharSequence, replacement: String?): String {
            val result = StringBuilder()
            var i = 0
            while (i < text.length) {
                var node: TrieNode? = root
                var j = i
                var endNode: TrieNode? = null
                var endIndex = -1
                while (j < text.length && node!!.children[text[j]] != null) {
                    node = node.children[text[j]]
                    if (node!!.isEndOfWord) {
                        endNode = node
                        endIndex = j
                    }
                    j++
                }
                if (endNode != null) {
                    result.append(replacement)
                    i = endIndex + 1
                } else {
                    result.append(text[i])
                    i++
                }
            }
            return result.toString()
        }
    }
}

fun StrReplacer.Companion.trieKeyword(keyWords: String,repToString: String = "") = TrieKeywordReplacer(keyWords)